|
数据结构之二维链表、队列和栈 -----Day19 and Day 20
一. 知识点整理1. 二维链表1.1 图解二维链表1.2 二维链表的一些操作（以MP3歌单项目为例）
1.3 队列3. 栈3.1 栈的理解3.2 通过链表的形式来实现对栈的操作
二. 重难点问题1. 如何将四则运算中的中缀如何转换成后缀形式（个位数字的四则运算）？
三. 自我总结
一. 知识点整理
1. 二维链表
1.1 图解二维链表
创建一个双向链表和一个单链表，其中双向链表中又保存单链表的指针，相当于创建一个歌单，和歌单里面的歌曲一样
代码如下
//定义的一维链表的结构体
typedef struct node
{
char *name;
struct node *next; //定义结构体的指针，单向指针，保存下一个结点的地址
}NODE;
//定义二维链表的结构体
typedef struct hnode
{
char *name;
int num;
NODE *top;
NODE *tail;
struct hnode *next; //定义结构体的指针,双向指针
struct hnode *prior;
}HNODE;
1.2 二维链表的一些操作（以MP3歌单项目为例）
仅展示部分核心代码，望见谅！
初始化二维链表的头结点
HNODE *InitHeadNode()
{
//给头节点分配内存
HNODE *head = (HNODE *)malloc(sizeof(HNODE));
assert(head != NULL);
//给头节点初始化
head->name = NULL;
head->num = -9999;
//双向节点初始化
head->next = head;
head->prior = head;
return head;
}
向二维链表中添加数据，添加歌单
int addHList(HNODE *head, const char *hname)
{
HNODE *temp = head->next; //定义一个中间指针用来判断添加的歌单和存在的歌单是否重复
//判断是否重复，重复则返回1
while (temp != head)
{
if (!strcmp(temp->name, hname))
{
printf("歌单已经存在，添加失败！\n");
return 1;
}
temp = temp->next;
}
//分配一个新的内存pnew用来保存要添加的歌单
HNODE *pnew = (HNODE *)malloc(sizeof(HNODE));
pnew->name = (char *)malloc(strlen(hname)+1);
assert(pnew != NULL);assert(pnew->name != NULL);
//给pnew赋值
strcpy(pnew->name, hname);
pnew->num = 0;
//连接到一起
pnew->prior = head->prior;
head->prior->next = pnew;
pnew->next = head;
head->prior = pnew;
}
向二维链表中添加链表，也就是向歌单中添加歌曲
int addMusic(HNODE *p, const char *mname)
{
NODE *pnew = (NODE *)malloc(sizeof(NODE));
pnew->name = (char *)malloc(strlen(mname)+1);
assert(pnew->name != NULL);
assert(pnew != NULL);
strcpy(pnew->name, mname);
if (isMPlistEmpty(p))
{
p->top = pnew;
}
else
{
p->tail->next = pnew;
}
p->tail = pnew;
pnew->next = NULL;
}
删除二维链表中的链表，也就是删除歌单中的歌曲
int delMusic(HNODE *h, const char *mname)
{
if (isMPlistEmpty(h))
{
return 0;
}
NODE *p = h->top;
NODE *q = NULL;
while (p != NULL)
{
if (!strcmp(p->name, mname)) //此处需要分类讨论，因为在二维链表中删除链表有多种可能
{
if (h->top == p && h->tail == p) //当删除的结点为第一个结点，同时也为最后一个节点是
{
h->top = NULL;
h->tail = NULL;
}
else if (p == h->top) //当删除的结点为第一个结点，但不为最后一个结点
{
h->top = p->next;
}
else if (p == h->tail) //当删除的结点为最后一个结点，但不为第一个结点
{
q->next = NULL;
h->tail = q;
}
else //中间的结点
{
q->next = p->next;
}
freeNode(p);
break;
}
q = p;
p = p->next;
}
}
清空二维链表，也就是清空歌单内的所有歌曲
void clearList(HNODE *p)
{
NODE *q = p->top;
while (q != NULL)
{
p->top = q->next;
freeNode(q);
q = p->top;
}
p->top = NULL;
p->tail = NULL;
p->num = 0;
}
销毁链表，也就是彻底删除歌单
void destroyAllList(HNODE **head)
{
HNODE *p = (*head)->next;
while (p != *head)
{
destroyList(*head, p->name);
p = (*head)->next;
}
free(*head);
*head = NULL;
}
打印二维链表里的所有内容，也就是打印所有歌单以及每个歌单内的歌曲
void printHList(HNODE *head)
{
HNODE *p = head->next;
while (p != head)
{
printf("歌单名：%s 歌曲数量：%d\n", p->name, p->num);
NODE *q = p->top;
while (q != NULL)
{
printf("%s\n", q->name);
q = q->next;
}
p = p->next;
}
}
以上代码均以展示核心内容为主
1.3 队列
队列的基本知识
队列是一个有序列表，可以用数组或者链表实现,遵循先入先出原则;即先存入队列的数据要先取出，后存入的要后取出,就好比日常生活中我们排队买票一样，正常情况下先到的人可以先买，后到的人只能后买；
链表实现队列代码ruxai文件所包含的库文件
#include
#include
#include
#include
创建队列以及队列的操作
//定义链表的结点
typedef struct node
{
int data;
struct node *next;
}NODE;
typedef struct queue
{
NODE *head;
NODE *tail;
}QUEUE;
//初始化队列的头结点
QUEUE *createQueue()
{
QUEUE *mqueue = (QUEUE *)malloc(sizeof(QUEUE));
assert(mqueue != NULL);
mqueue->head = NULL;
mqueue->tail = NULL;
return mqueue;
}
//判断队列是否为空
int isEmptyQueue(QUEUE *queue)
{
if (queue->head == NULL)
{
return 0; //表示为空
}
return 1;
}
//向队列中添加数据——入队
void addQueue(QUEUE *queue, int data)
{
NODE *pnew = (NODE *)malloc(sizeof(QUEUE));
assert(pnew != NULL);
pnew->data = data;
pnew->next = NULL;
if (!isEmptyQueue(queue))
{
queue->head = pnew;
queue->tail = pnew;
}
else
{
queue->tail->next = pnew;
queue->tail = pnew;
}
}
//出队
void delQueue(QUEUE *queue)
{
NODE *temp = queue->head;
if (!isEmptyQueue(queue))
{
printf("队列已经为空！\n");
return ;
}
else
{
queue->head = temp->next;
queue->tail = NULL;
}
free(temp);
}
//打印队列
void printQueue(QUEUE *queue)
{
NODE *q = queue->head;
while (q != NULL)
{
printf("%d \n", q->data);
q = q->next;
}
}
//获取队列的第一个元素的值
int getHeadQueue(QUEUE *queue)
{
int headNum;
NODE *q = queue->head;
if (q != NULL)
{
headNum = q->data;
}
return headNum;
}
//清空队列
void clrQueue(QUEUE *queue)
{
while (isEmptyQueue(queue))
{
delQueue(queue);
if (queue->head == NULL)
{
break;
}
}
}
//销毁整个队列
void destroyQueue(QUEUE **queue)
{
clrQueue(*queue);
QUEUE *temp = *queue;
*queue = NULL;
free(temp);
}
测试函数
int main(int argc, char const *argv[])
{
QUEUE *mqueue = createQueue();
printf("-------进入队列打印-------\n");
addQueue(mqueue, 5);
addQueue(mqueue, 2);
addQueue(mqueue, 0);
printf("\n");
printQueue(mqueue);
printf("-------出队列打印-------\n");
delQueue(mqueue);
printf("\n");
printQueue(mqueue);
printf("-------清空队列打印-------\n");
clrQueue(mqueue);
printf("\n");
printQueue(mqueue);
printf("-------销毁队列-------\n");
destroyQueue(&mqueue);
printf("\n");
printQueue(mqueue);
return 0;
}
3. 栈
3.1 栈的理解
栈通俗一点其实就是一个后进先出的线性表，就比如你往水杯里面放口径一样大的镜片，先放进去的最后才能拿出来；
3.2 通过链表的形式来实现对栈的操作
文件所包含的库文件
#include
#include
#include
#include
栈的定义初始化以及操作
typedef struct node
{
int data;
struct node *next;
}NODE;
typedef struct stack
{
NODE *top;
}STACK;
STACK *createStack()
{
STACK *mstack = (STACK *)malloc(sizeof(STACK));
assert(mstack != NULL);
mstack->top = NULL;
return mstack;
}
int isEmptyStack(STACK *mstack)
{
if (mstack->top == NULL)
{
return 1;
}
return 0;
}
void pushStack(STACK *mstack, int data)
{
NODE *pnew = (NODE *)malloc(sizeof(NODE));
assert(pnew != NULL);
pnew->data = data;
pnew->next = NULL;
if (isEmptyStack(mstack))
{
mstack->top = pnew;
}
else
{
pnew->next = mstack->top;
mstack->top = pnew;
}
}
void popStack(STACK *mstack)
{
if (isEmptyStack(mstack))
{
printf("空栈，无需删除！\n");
}
else
{
NODE *temp = mstack->top;
mstack->top = temp->next;
free(temp);
}
}
void printStack(STACK *mstack)
{
NODE *p = mstack->top;
while (p != NULL)
{
printf("%d\n", p->data);
p = p->next;
}
}
int getTopStack(STACK *mstack)
{
NODE *p = mstack->top;
int top_num;
if (p != NULL)
{
top_num = p->data;
}
return top_num;
}
void clearStack(STACK *mstack)
{
while (isEmptyStack(mstack))
{
popStack(mstack);
}
}
void destroyStack(STACK **mstack)
{
clearStack(*mstack);
free(*mstack);
*mstack = NULL;
}
测试代码
int main(int argc, char const *argv[])
{
QUEUE *mqueue = createQueue();
printf("-------进入队列打印-------\n");
addQueue(mqueue, 5);
addQueue(mqueue, 2);
addQueue(mqueue, 0);
printf("\n");
printQueue(mqueue);
printf("-------出队列打印-------\n");
delQueue(mqueue);
printf("\n");
printQueue(mqueue);
printf("-------清空队列打印-------\n");
clrQueue(mqueue);
printf("\n");
printQueue(mqueue);
printf("-------销毁队列-------\n");
destroyQueue(&mqueue);
printf("\n");
printQueue(mqueue);
return 0;
}
二. 重难点问题
1. 如何将四则运算中的中缀如何转换成后缀形式（个位数字的四则运算）？
可以参考一下几个步骤
第一步：对要进行运算的式子进行遍历 第二步：当遇到左括号时，直接将括号压入到栈 第三步：当遇到计算的数字字符时，直接添加到队列；遇到算数运算符号时需要比较优先级：
当栈中没有运算符号时，直接压入栈中，当栈中栈顶的运算符号的优先级比较低时，也直接压入栈中；当栈顶的运算符号的优先级高于时，则需要先将栈中的运算符号出栈，然后加入到队列中；如果栈中还有运算符号则接着进行比较； 第四步：当遇到右括号时，将栈内的运算符号逐个取出，并加入到队列，直到遇到与之配对的括号，将括号废除；
对后缀形式的式子进行运算处理：
第一步：当遇到数字符号时，将其压入到栈中 第二步：当遇到运算符号时，将栈中与之最近的两个数字取出来进行运算，形式为“左数 运算符号 右数”， 运算结束将结果继续压入栈中； 第三步：将所有符号与数字处理完则剩下结果
三. 自我总结
但是我也收获了很多，对一些更高级的知识有了憧憬，比如链表相比数组的优点和独立性，队列和栈在解决一些现实问题的实用性。 学习完二维链表、栈还有队列之后，怎么说可以说是被打的溃不成军，很多知识点又难又复杂，就像转迷宫一样；
|